Digital systems are often controlled by event-driven techniques, such as a parallel or sequential networks that advance from one "state" to the next according to a predetermined sequence. Hence, these digital systems, together with the states and event driven techniques, are often called finite state machines. The advancement from a present state to a next state of a finite state machine can be in response to clock pulses, such as in a synchronous state machine, or to other criteria, such as interrupt requests in an asynchronous state machine. Traditionally, progression through the state machine is a function of an input and the present state.
Finite state machines are often used for modeling telecommunication systems. For example, a network switch using Integrated Services Digital Network User Part (ISUP) for controlling a call may utilize a finite state machine. Current ISUP messages include: an initial address message (IAM), a continuity check message (COT), an address complete message (ACM), an answer message (ANM), a release message (REL), and a release complete message (RLC). Each message can be represented as a state of the finite state machine and a call may progress sequentially through multiple combinations of the states. For example, a call can progress from the ANM state, to the REL state, and then to the RLC state.
Difficulties arise when streams of concurrent calls, or "message streams," exist. Typical state machines have a restriction that only one message stream is supported at a time. Therefore, to model concurrent message streams, the typical state machine must be duplicated, one for each message stream. However, considering a state machine that has P states and Q transitions between the states, if there are N concurrent message streams, the multiple copies of the state machine will have N.times.P states and N.times.Q+(N.times.P).times.((N-1).times.P) transitions. The (N.times.P).times.((N-1).times.P) transitions are required because the digital system performing the transitions, in response to received inputs, must logically move between each of the states in each of the state machines, thereby requiring transitions between every state.
Referring to FIG. 1, an exemplary conventional state machine 10 has four states S0, S1, S2, S3 representing individual actions to be performed. The exemplary state machine 10 also has six transitions Tij, where the letter "i" designates a present state Si and the letter "j" designates a next state Sj. State S0 represents an initial state from which the state machine 10 is entered.
Referring also to FIG. 2, to handle three concurrent message streams, the exemplary state machine 10 (FIG. 1) must be duplicated to produce three state machines 10a, 10b, and 10c, (the states in each state machine include the suffix a, b, c corresponding to the state machine 10a, 10b, 10c, respectively). All the transitions are also duplicated. However, additional transitions are also required to link a state of each state machine to every state of every other state machine. For example, the state S1c of the state machine 10c includes additional links to S0a, S1a, S2a, S3a, S0b, S1b, S2b, S3b. There are eighty eight additional links which are not shown, for the sake of clarity.
Therefore, it becomes immediately evident that as the number of concurrent message streams and/or the number of states increase, the multiple state machines become too large to be efficiently managed.